home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8310 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.3 KB
  1. Path: news.iconn.net!news
  2. From: thecrow@iconn.net (The Crow)
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 16 Feb 1996 19:06:15 GMT
  6. Organization: I rule the world
  7. Message-ID: <4g2kj8$1sg@news.iconn.net>
  8. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com> <4fv74c$chq@gatekeeper.alcatel.no>
  9. NNTP-Posting-Host: st-ts00-01.iconn.net
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=US-ASCII
  12. X-Newsreader: WinVN 0.99.6
  13.  
  14. In article <4fv74c$chq@gatekeeper.alcatel.no>, Sven.Pran@alcatel.noL says...
  15. >
  16. >In article <31224679.6193@born.com>, John Cleland <clelaj@born.com> wrote:
  17. >>The Crow wrote:
  18. >>> 
  19. >>> Here is what I am trying to do, I want to find the last NON-ZERO digit of a
  20. >>> given factorial.  For instance,
  21. >>> 
  22. >>> 5! = 120
  23. >>> 
  24. >>> so the last non-zero digit is 2.  I want to be able to do this up to 1000.
  25. >>> Problem is, no matter how huge of a data-type you use, there isn't any way 
  26. >>> for the computer to handle 1000!, it is however possible to find the last 
  27. >>> non-zero digit somehow.  One thing I have tried is as I went through 
  28. >>> multiplying the series of numbers in the factorial (5 * 4 * 3 * 2) I would 
  29. >>> remove all the trailing ZEROS, I got this to work up to 789, but it wont 
  30. >>> work with 1000 and i am not really sure why.  If anyone has a clue how I 
  31. >>> can do this let me know.
  32. >>
  33. >>Don't just strip the trailing zeros, remove all digits except the last 
  34. >>non-zero digit (which is your output) and then multiply by the next number in 
  35. >>your sequence. This keeps the numbers down to a managable level and gives the 
  36. >>correct answer as no more significant digit can affect the value of the LSD.
  37. >>
  38. > . . . .
  39. >
  40. >No, it is obviously not sufficient to keep the last single non-zero digit, and 
  41. >the problem appears to be a very interesting and intriguing one:
  42. >
  43. >A new trailing zero is 'created' every time the next multiplier is divisible 
  44. >by 5, and how can we then calculate the next 'rightmost significant' digit?
  45. >
  46. >Example when a multiplier ends in 05:
  47. >
  48. >If the 'previous' factorial ended in 02 then the new factorial will end in 1 
  49. >while if it ended in 12 then the new factorial will end in 6 (after removal of 
  50. >trailing zeroes).
  51. >
  52. >Thus the SINGLE rightmost significant digit in the new factorial depends upon 
  53. >the TWO rightmost significant digits both in the previous factorial and in the 
  54. >multiplier.
  55. >
  56. >This means that we must keep track of the last TWO digits to calculate the new 
  57. >SINGLE rightmost significant digit whenever a zero is 'created'. For similar 
  58. >reasons we must track THREE digits to calculate the new TWO rightmost 
  59. >significant digits - and so on.
  60. >
  61. >How many zeroes have been 'removed' when we reach 1000! ? The answer is 249, 
  62. >which means that in order to maintain the precision needed we must track the 
  63. >last 250 digits less the number of zeroes already 'removed' when N! reaches a 
  64. >number with that many digits.
  65. >
  66. >This is where I get stuck. Hey - number theory specialists: How do we proceed?
  67. >
  68. >regards Sven
  69. I got it working, it is actually fairly easy, first you remove EVERY zero from 
  70. the number, not just trailing ones (converting the number to a string and back 
  71. again makes this easy) next you remove all but the last 3 digits, and walla. it 
  72. works.
  73.  
  74.  
  75.  
  76. -- 
  77. The Crow - thecrow@iconn.net
  78. "It can't rain all the time"
  79. -Kryptology
  80.  
  81.